public class Tests {
    /**
     * Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands which the sum of 1‘s on the island equal S (S>0).
     * An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
     * You may assume all four edges of the grid are all surrounded by water.
     * Example 1:
     * Input: grid = [
     *  ["1","1","1","1","0"],
     *  ["1","1","0","1","0"],
     *  ["1","1","0","0","0"],
     *  ["0","0","0","0","0"]
     * ], S = 9
     * Output: 1
     * public int sumIslands(char[][] grid, int S){
     *   // implementation
     * }
     *
     */
    //----------
    // unit test
    //----------
    //    Tip: using Junit4.
    @org.junit.Test
    public void sumIslandsTest(){
        char[][] grid = {
                {'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','0','0','0'}
        };
        int S = 9;
        // test implementation

        //测试样例条件下 S=9
        int result4Grid9 = sumIslandsCount(deepClone(grid), S);
        System.out.printf("样例岛屿结构下 S = %d, 结果: %d%n", S, result4Grid9);

        //测试样例条件下 S=8
        int S2 = 8;
        int result4Grid8 = sumIslandsCount(deepClone(grid), S2);
        System.out.printf("样例岛屿结构下 S = %d, 结果: %d%n", S2, result4Grid8);

        char[][] gridSnd = {
                {'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','1'}
        };

        int S3 = 1;
        int result4GridSnd1 = sumIslandsCount(deepClone(gridSnd), S3);
        System.out.printf("新设定岛屿结构下 S = %d, 结果: %d%n", S3, result4GridSnd1);

    }

    /**
     * 满足面积等于 sumStandard的岛屿总数
     * @param grid 岛屿信息坐标数组
     * @param sumStandard 面积标准
     * @return 满足条件的岛屿数量
     */
    private int sumIslandsCount(char[][] grid, int sumStandard){
        int resultCount = 0;
        for (int rowIndex = 0; rowIndex < grid.length; rowIndex++) {
            for (int colIndex = 0; colIndex < grid[rowIndex].length; colIndex++) {
                if (grid[rowIndex][colIndex] == '1' && sumIslandsItemCount(grid, rowIndex, colIndex) == sumStandard){
                    resultCount++;
                }
            }
        }
        return resultCount;
    }

    /**
     * 包含(rowIndex, colIndex)坐标的岛屿的面积(已去重)
     * @param grid 岛屿信息坐标数组
     * @param rowIndex 行坐标
     * @param colIndex 列坐标
     * @return 岛屿总面积
     */
    private int sumIslandsItemCount(char[][] grid, int rowIndex, int colIndex){
        int rowSize = grid.length;
        int colSize = grid[0].length;
        if (!isInGrid(rowSize, colSize, rowIndex, colIndex) || grid[rowIndex][colIndex] != '1'){
            return 0;
        }
        grid[rowIndex][colIndex] = 'x'; //去重
        return 1 + //自身
                sumIslandsItemCount(grid, rowIndex - 1, colIndex) + //上
                sumIslandsItemCount(grid, rowIndex + 1, colIndex) + //下
                sumIslandsItemCount(grid, rowIndex, colIndex - 1) + //左
                sumIslandsItemCount(grid, rowIndex, colIndex + 1); //右


    }

    /**
     * 判断(rowIndex, colIndex)是否在岛屿范围内
     * @param rowSize 行容量
     * @param colSize 列容量
     * @param rowIndex 行坐标
     * @param colIndex 列坐标
     * @return 是否在岛屿范围内
     */
    private boolean isInGrid(int rowSize, int colSize, int rowIndex, int colIndex){
        return rowIndex < rowSize && rowIndex >= 0 && colIndex < colSize && colIndex >= 0;
    }

    /**
     * 深度拷贝二元数组
     * @param source 源数组
     * @return 目标数组
     */
    private char[][] deepClone(char[][] source){
        char[][] target = new char[source.length][source[0].length];
        for (int i = 0; i < source.length; i++) {
            target[i] = source[i].clone();
        }
        return target;
    }

}